/******************************************************************************
 * Shared utilities for search engine scripts.
 *****************************************************************************/

(function (root, factory) {
  // Browser globals
  root.utils = factory(root.utils);
}(this, function (utils) {

'use strict';

const SYNONYM_HANDLER_PARSER_REGEX = new RegExp([
  '\\\\(?:u(?:[0-9A-Fa-f]{4}|\\{[0-9A-Fa-f]+\\})|x[0-9A-Fa-f]{2}|[0-3][0-7]{0,2}|[4-7][0-7]{0,1}|c[A-Za-z]|[pP]\\{[A-Za-z]+\\}|k<[^>]*>|[A-Za-z])',
  '(\\\\.)', // group 1
  '\\(\\?(?:[:!=]|<(?:[=!]|[^>]*>))',
  '\\[[^\\\\\\]]*(?:\\\\.[^\\\\\\]]*)*\\]',
  '\\{\\d+(?:,\\d*)?\\}',
  '[/^$*+?.|()[\\]{}]',
].join('|'), 'gu');
const SYNONYM_HANDLER_SINGLE_CHAR_REGEX = /^[\s\S]$/u;

/** @public */
class SynonymHandler {
  constructor(data) {
    // validate data
    if (!(typeof data === 'object' && data !== null && !Array.isArray(data))) {
      throw new Error(`輸入資料須為一物件。`);
    }

    for (const [key, value] of Object.entries(data)) {
      if (!(Array.isArray(value) && value.every(x => typeof x === 'string'))) {
        throw new Error(`輸入資料含有非字串陣列的鍵值："${key}": ${JSON.stringify(value)}`);
      }
    }

    /** @private */
    this.raw = data;
  }

  /** @public */
  static async fromSources(urls) {
    const data = {};
    for (let url of urls) {
      let json;
      try {
        json = (await utils.xhr({
          url,
          responseType: 'json',
          overrideMimeType: 'application/json',
        })).response;
      } catch (ex) {
        throw new Error(`unable to load '${url}': ${ex.message}`);
      }
      Object.assign(data, json);
    }
    return new SynonymHandler(data);
  }

  /** @public */
  get data() {
    return this.raw;
  }

  /** @private */
  init() {
    const synonyms = this.raw;
    const synonymsEscaped = {};
    let synonymsEscapedMaxLen = -Infinity;

    for (let key of Object.keys(synonyms)) {
      const values = synonyms[key].slice();
      values.unshift(key);
      key = utils.escapeRegExp(key);
      synonymsEscapedMaxLen = Math.max(synonymsEscapedMaxLen, key.length);
      synonymsEscaped[key] = values.map(utils.escapeRegExp);
    }

    this.synonymList = synonymsEscaped;
    this.synonymMaxLen = Math.max(synonymsEscapedMaxLen, 1);

    // replace with bull for lazy execution
    this.init = null;
  }

  /**
   * 將 regexStr 中的字串取代為可比對任一異體字
   *
   * - 略過 [...]，因 [A] 轉為 [(?:A1|A2)] 會造成語義錯誤
   * - 略過 \ooo, \xhh, \uhhhh, \cX, \X，因無原始字元，無法與轉換表正常比對
   * - 保留 "\" + 原始字元 的跳脫形式
   *
   * @public
   */
  convert(regexStr) {
    this.init && this.init();
    const result = [];
    let lastIndex = SYNONYM_HANDLER_PARSER_REGEX.lastIndex = 0;
    while (SYNONYM_HANDLER_PARSER_REGEX.test(regexStr)) {
      const m = RegExp.lastMatch;
      if (RegExp.$1) { continue; }
      const delta = regexStr.substring(lastIndex, SYNONYM_HANDLER_PARSER_REGEX.lastIndex - m.length);
      result.push(this.convertPart(delta));
      result.push(m);
      lastIndex = SYNONYM_HANDLER_PARSER_REGEX.lastIndex;
    }
    const delta = regexStr.substring(lastIndex);
    result.push(this.convertPart(delta));
    return result.join('');
  }

  /**
   * Apply synonym list on a safe regex str
   *
   * @private
   */
  convertPart(str) {
    const {synonymList, synonymMaxLen} = this;
    const output = [];
    outer:
    for (let i = 0, I = str.length; i < I; i++) {
      let s = str.substr(i, synonymMaxLen);
      for (let j = synonymMaxLen; j >= 1; j--) {
        s = s.substr(0, j);
        let v = synonymList[s];
        if (v) {
          s = v.every(x => SYNONYM_HANDLER_SINGLE_CHAR_REGEX.test(x)) ?
              `[${v.join('')}]` :
              `(?:${v.join('|')})`;
          output.push(s);
          i += j - 1;
          continue outer;
        }
      }
      output.push(s);
    }
    return output.join('');
  }
}

const NOPUNC_HANDLER_PARSER_REGEX = new RegExp([
  '\\\\(?:u(?:[0-9A-Fa-f]{4}|\\{[0-9A-Fa-f]+\\})|x[0-9A-Fa-f]{2}|[0-3][0-7]{0,2}|[4-7][0-7]{0,1}|c[A-Za-z]|[pP]\\{[A-Za-z]+\\}|k<[^>]*>|[A-Za-z])',
  '(\\\\.)', // group 1
  '\\(\\?(?:[:!=]|<(?:[=!]|[^>]*>))',
  '\\[[^\\\\\\]]*(?:\\\\.[^\\\\\\]]*)*\\]',
  '\\{\\d+(?:,\\d*)?\\}',
  '[/^$*+?.|()[\\]{}]',
].join('|'), 'gu');
const NOPUNC_HANDLER_UNESCAPER_REGEX = /\\(\.)/g;

/** @public */
class NoPuncHandler {
  constructor(regexStr) {
    this.raw = regexStr;
    this.noPuncRegex = new RegExp(regexStr, 'migu');
    this.noPuncSep = '(?:' + regexStr + ')*';
  }

  /** @public */
  static get DEFAULT_NOPUNC_REGEX() {
    // Unicode property escapes supported since Firefox >= 78, Chromium >= 64
    const SUPPORT_REGEXP_UNICODE_PROPERTY_ESCAPES = (() => {
      try {
        new RegExp('\\p{L}\\p{N}', 'u');
      } catch (ex) {
        return false;
      }
      return true;
    })();

    const value = SUPPORT_REGEXP_UNICODE_PROPERTY_ESCAPES ?
      '[^\\p{L}\\p{N}]' :
      '[' + [
        '\\s\\x00-\\x2F\\x3A-\\x40\\x5B-\\x60',
        '\\u2000-\\u27FF\\u2900-\\u2BFF',
        '\\u3001\\u3002\\u3008-\\u3021\\u3190-\\u319F\\u3200-\\u33FF\\u4DC0-\\u4DFF',
        '\\uFE10-\\uFE6F',
        '\\uFF00-\\uFF0F\\uFF1A-\\uFF20\\uFF3B-\\uFF40\\uFF5B-\\uFF65',
        '\\uFFE0-\\uFFFF',
      ].join('') + ']';
    Object.defineProperty(NoPuncHandler, 'DEFAULT_NOPUNC_REGEX', {value});
    return value;
  }

  /** @public */
  get data() {
    return this.raw;
  }

  /**
   * 將 regexStr 中的字串取代為忽略標點（或字元）
   *
   * @public
   */
  convert(regexStr) {
    const stack = [];
    let lastIndex = NOPUNC_HANDLER_PARSER_REGEX.lastIndex = 0;
    while (NOPUNC_HANDLER_PARSER_REGEX.test(regexStr)) {
      const m = RegExp.lastMatch;
      if (RegExp.$1) { continue; }
      const delta = regexStr.substring(lastIndex, NOPUNC_HANDLER_PARSER_REGEX.lastIndex - m.length);
      if (delta) { stack.push(this.insertSep(delta)); }
      stack.push(m);
      lastIndex = NOPUNC_HANDLER_PARSER_REGEX.lastIndex;
    }
    const delta = regexStr.substring(lastIndex);
    if (delta) { stack.push(this.insertSep(delta)); }

    // "*"、"+"、"?"、"{" 前不可加 sep
    // (..x|y|z) 視為一單位，故 "(.." 後、"|" 前後、")" 前可省略 sep
    const result = [];
    for (let i = stack.length; i--;) {
      if (["(", "|"].includes(stack[i][0])) {
        result[0] = stack[i] + result[0];
      } else if (result.length && [")", "|", "*", "+", "?", "{"].includes(result[0][0])) {
        result[0] = stack[i] + result[0];
      } else {
        result.unshift(stack[i]);
      }
    }

    return result.join(this.noPuncSep);
  }

  /** @private */
  insertSep(str) {
    let s = str;
    s = s.replace(NOPUNC_HANDLER_UNESCAPER_REGEX, '$1');
    s = s.replace(this.noPuncRegex, '');
    s = Array.from(s).map(utils.escapeRegExp).join(this.noPuncSep);
    return s;
  }
}

const COMPLEX_QUERY_PARSER_REGEX = new RegExp([
  '((?:^|\\s+)AND(?=\\s|$))', // group 1
  '((?:^|\\s+)OR(?=\\s|$))', // group 2
  '(\\s*\\()', // group 3
  '(\\s*\\))', // group 4
  '\\s*((?:-*[A-Za-z]+:|-+)(?:"[^"]*(?:""[^"]*)*(?:"|$)|[^"()\\s]*)|"[^"]*(?:""[^"]*)*(?:"|$)|[^"()\\s]+)', // group 5
].join('|'), 'gui');
const COMPLEX_QUERY_PREFIX_NEGS_REGEX = /^(-+)(.*)$/;
const COMPLEX_QUERY_PREFIX_CMD_REGEX = /^([a-z]+):(.*)$/i;
const COMPLEX_QUERY_PREFIX_QUOTE_REGEX = /^"([^"]*(?:""[^"]*)*)"?$/i;
const COMPLEX_QUERY_PREFIX_QUOTE_REMOVER_REGEX = /""/g;
const COMPLEX_QUERY_ENTITY_NOOP = 0;
const COMPLEX_QUERY_ENTITY_AND = 1;
const COMPLEX_QUERY_ENTITY_OR = 2;
const COMPLEX_QUERY_ENTITY_NEG = 3;
const COMPLEX_QUERY_ENTITY_GROUP_OPEN = 4;
const COMPLEX_QUERY_ENTITY_GROUP_CLOSE = 5;
const COMPLEX_QUERY_CONDITION_MAP = new Map([
  [COMPLEX_QUERY_ENTITY_NOOP, '1'],
  [COMPLEX_QUERY_ENTITY_AND, '&&'],
  [COMPLEX_QUERY_ENTITY_OR, '||'],
  [COMPLEX_QUERY_ENTITY_NEG, '!'],
  [COMPLEX_QUERY_ENTITY_GROUP_OPEN, '('],
  [COMPLEX_QUERY_ENTITY_GROUP_CLOSE, ')'],
]);
const COMPLEX_QUERY_MATCH_KEYWORD_FUNC = (regex, data) => regex.test(data);

/** @public */
class ComplexQuery {
  constructor(queryStr, options) {
    this.query = queryStr;

    const query = this.parseOptions(queryStr, options);

    // 解析 queryStr，將資料儲存至 query
    let m;
    COMPLEX_QUERY_PARSER_REGEX.lastIndex = 0;
    while ((m = COMPLEX_QUERY_PARSER_REGEX.exec(queryStr))) {
      if (m[1] !== undefined) {
        query.stack[query.stack.length - 1].push(COMPLEX_QUERY_ENTITY_AND);
      } else if (m[2] !== undefined) {
        query.stack[query.stack.length - 1].push(COMPLEX_QUERY_ENTITY_OR);
      } else if (m[3] !== undefined) {
        query.stack.push([]);
      } else if (m[4] !== undefined) {
        this.popStackAndMerge(query);
      } else if (m[5] !== undefined) {
        this.parsePrefixedKeyword(m[5], query);
      }
    }
    this.rules = query.rules;

    // 逐層整併 query.stack 並將結果輸出至 query.condition
    for (let i = query.stack.length - 1; i > 0; i--) {
      this.popStackAndMerge(query);
    }
    this.condition = this.getCondition(query.stack[0]) || COMPLEX_QUERY_CONDITION_MAP.get(COMPLEX_QUERY_ENTITY_NOOP);

    // 驗證語法是否正確
    try {
      this.match(this.defaultMatchData);
    } catch(ex) {
      console.error(`Bad query: ${queryStr} => ${condition}`);
      console.error(ex);
      throw new Error(`檢索條件「${queryStr}」語法有誤。`);
    }

    this.parseFinalQuery(query);
  }

  /** @private */
  get defaultMatchData() {
    return '';
  }

  /** @public */
  match(data) {
    const test = COMPLEX_QUERY_MATCH_KEYWORD_FUNC;
    return eval(this.condition);
  }

  /** @private */
  parseOptions(queryStr, {
    ignoreCase = true, multiline = true, useRegex = false, useSynonyms = true, noPunc = false,
    synonymHandler = null, noPuncRegex = null,
  } = {}) {
    const regexFlag = (ignoreCase ? 'i' : '') + (multiline ? 'm' : '') + 'u';
    const noPuncHandler = noPuncRegex ? new utils.NoPuncHandler(noPuncRegex) : null;

    return {
      query: queryStr,
      stack: [[]],
      rules: {
        '': {
          patterns: [],
          hasCaptureGroup: false,
        },
      },
      regexFlag, useRegex,
      useSynonyms, synonymHandler,
      noPunc, noPuncHandler,
    };
  }

  /** @private */
  parsePrefixedKeyword(part, query) {
    part = part.trim();

    if (COMPLEX_QUERY_PREFIX_NEGS_REGEX.test(part)) {
      const negs = RegExp.$1;
      part = RegExp.$2;
      const stackTail = query.stack[query.stack.length - 1];
      for (let i = 0, I = negs.length; i < I; i++) {
        stackTail.push(COMPLEX_QUERY_ENTITY_NEG);
      }
    }

    let cmd = '';
    if (COMPLEX_QUERY_PREFIX_CMD_REGEX.test(part)) {
      cmd = RegExp.$1;
      part = RegExp.$2;
    }

    if (COMPLEX_QUERY_PREFIX_QUOTE_REGEX.test(part)) {
      part = (RegExp.$1).replace(COMPLEX_QUERY_PREFIX_QUOTE_REMOVER_REGEX, '"');
    }

    const command = this[`cmd_${cmd}`];
    command && command.call(this, part, query);
  }

  /** @private */
  parseBooleanCommandKeyword(keyword, query, options) {
    // -cmd:key 補成 --key 以免 key 變成負向
    if (this.getNeg(query)) {
      query.stack[query.stack.length - 1].push(COMPLEX_QUERY_ENTITY_NEG);
    }
    this.parseKeyword(keyword, query, options);
  }

  /** @private */
  parseKeyword(keyword, query, {
    field = '',
  } = {}) {
    const neg = this.getNeg(query);
    const {
      regexFlag, useRegex,
      useSynonyms, synonymHandler,
      noPunc, noPuncHandler,
    } = query;

    const q = new KeywordQuery(keyword, {
      regexFlag, useRegex,
      noPuncHandler: noPunc ? noPuncHandler : null,
      synonymHandler: useSynonyms ? synonymHandler : null,
    });

    if (q.regex) {
      const test = field ? `test_${field}` : 'test';
      const cond = `${test}(/${q.regex.source}/${q.regex.flags},data)`
      query.stack[query.stack.length - 1].push(cond);
      if (!neg) {
        const regex = new RegExp(q.regex.source, regexFlag + 'g');
        query.rules[field].patterns.push(regex);
        if (q.hasCaptureGroup) {
          query.rules[field].hasCaptureGroup = true;
        }
      }
    }
  }

  /** @private */
  parseFinalQuery(query) {
    // NOOP, for extension
  }

  /**
   * Get current negativity of query.
   *
   * @private
   */
  getNeg(query) {
    const stackTail = query.stack[query.stack.length - 1];
    let neg = false;
    for (let i = stackTail.length - 1; i >= 0; i--) {
      if (stackTail[i] !== COMPLEX_QUERY_ENTITY_NEG) {
        break;
      }
      neg = !neg;
    }
    return neg;
  }

  /**
   * Pop the stack tail, convert it into condition, and merge into the previous
   * stack item.
   *
   *@private
   */
  popStackAndMerge(query) {
    if (query.stack.length <= 1) { return; }
    const stackTail = query.stack.pop();
    const condition = this.getCondition([COMPLEX_QUERY_ENTITY_GROUP_OPEN, ...stackTail, COMPLEX_QUERY_ENTITY_GROUP_CLOSE]);
    query.stack[query.stack.length - 1].push(condition);
  }

  /**
   * Get the output condition of a stack item array.
   *
   * @private
   */
  getCondition(stackItem) {
    const rv = [];

    let current = null;
    let prev = null;
    for (let i = 0, I = stackItem.length; i < I; i++) {
      current = stackItem[i];

      if (typeof current === 'string' || current === COMPLEX_QUERY_ENTITY_NEG) {
        if (typeof prev === 'string') {
          rv.push(COMPLEX_QUERY_CONDITION_MAP.get(COMPLEX_QUERY_ENTITY_AND));
        }
      } else if (current === COMPLEX_QUERY_ENTITY_AND || current === COMPLEX_QUERY_ENTITY_OR ||
          current === COMPLEX_QUERY_ENTITY_GROUP_CLOSE) {
        if (prev === COMPLEX_QUERY_ENTITY_AND || prev === COMPLEX_QUERY_ENTITY_OR ||
            prev === COMPLEX_QUERY_ENTITY_NEG || prev === COMPLEX_QUERY_ENTITY_GROUP_OPEN ||
            prev === null) {
          rv.push(COMPLEX_QUERY_CONDITION_MAP.get(COMPLEX_QUERY_ENTITY_NOOP));
        }
      }

      rv.push(COMPLEX_QUERY_CONDITION_MAP.get(current) || current);

      prev = current;
    }

    if (current === COMPLEX_QUERY_ENTITY_AND || current === COMPLEX_QUERY_ENTITY_OR || current === COMPLEX_QUERY_ENTITY_NEG) {
      rv.push(COMPLEX_QUERY_CONDITION_MAP.get(COMPLEX_QUERY_ENTITY_NOOP));
    }

    return rv.join(' ');
  }

  /** @private */
  cmd_(keyword, query) {
    this.parseKeyword(keyword, query);
  }

  /** @private */
  cmd_re(keyword, query) {
    query.useRegex = !this.getNeg(query);
    this.parseBooleanCommandKeyword(keyword, query);
  }

  /** @private */
  cmd_syn(keyword, query) {
    query.useSynonyms = !this.getNeg(query);
    this.parseBooleanCommandKeyword(keyword, query);
  }

  /** @private */
  cmd_np(keyword, query) {
    query.noPunc = !this.getNeg(query);
    this.parseBooleanCommandKeyword(keyword, query);
  }
}

const KEYWORD_QUERY_CAPTURE_GROUP_REGEX = new RegExp([
  '\\\\(?:k<[^>]*>|.)',
  '\\[[^\\\\\\]]*(?:\\\\.[^\\\\\\]]*)*\\]',
  '(\\((?:(?!\\?)|\\?<[^>]*>))',
].join('|'), 'gu');

/** @public */
class KeywordQuery {
  constructor(queryStr, {
      regexFlag = 'imu', useRegex = false, synonymHandler, noPuncHandler,
    } = {}) {
    this.query = queryStr;
    this.regex = null;
    this.hasCaptureGroup = false;

    let key = queryStr;

    if (useRegex) {
      KEYWORD_QUERY_CAPTURE_GROUP_REGEX.lastIndex = 0;
      while (KEYWORD_QUERY_CAPTURE_GROUP_REGEX.test(key)) {
        if (RegExp.$1) {
          this.hasCaptureGroup = true;
          break;
        }
      }
      try {
        new RegExp(key, regexFlag);
      } catch(ex) {
        console.error(`Bad keyword regex: ${queryStr} => /${key}/${regexFlag}`);
        throw new Error(`正規表示式「${queryStr}」語法有誤。`);
      }
    } else {
      key = utils.escapeRegExp(key);
    }

    if (synonymHandler) { key = synonymHandler.convert(key); }
    if (noPuncHandler) { key = noPuncHandler.convert(key); }
    if (!key) { return; }

    this.regex = new RegExp(key, regexFlag);
  }

  /** @public */
  match(text) {
    return !this.regex || this.regex.test(text);
  }
}

const DATE_QUERY_PARSER_REGEX = /^(-?\d*)(\/?)(-?\d*)$/;
const DATE_QUERY_MATCHER_REGEX = /^(-?\d{0,4})(?:[^\/]*)(\/?)(-?\d{0,4})(?:[^\/]*)$/;

/** @public */
class DateQuery {
  constructor(queryStr) {
    if (!DATE_QUERY_PARSER_REGEX.test(queryStr)) {
      throw new Error(`年份「${queryStr}」語法有誤。`);
    }

    this.query = queryStr;

    if (RegExp.$2.length) {
      this.min = RegExp.$1.length ? parseInt(RegExp.$1, 10) : -Infinity;
      this.max = RegExp.$3.length ? parseInt(RegExp.$3, 10) : Infinity;
    } else {
      this.min = this.max = parseInt(RegExp.$1, 10);
    }

    if (this.max < this.min) {
      [this.min, this.max] = [this.max, this.min];
    }
  }

  /** @public */
  match(text) {
    if (!DATE_QUERY_MATCHER_REGEX.test(text)) { return false; }

    let min, max;
    if (RegExp.$2.length) {
      min = RegExp.$1.length ? parseInt(RegExp.$1, 10) : -Infinity;
      max = RegExp.$3.length ? parseInt(RegExp.$3, 10) : Infinity;
    } else {
      min = max = parseInt(RegExp.$1, 10);
    }

    if (min > max) { return false; }

    return this.min <= max && min <= this.max;
  }
}

const QUALITY_QUERY_PARSER_REGEX = /^(-?\d*)(\/?)(-?\d*)$/;
const QUALITY_QUERY_MATCHER_REGEX = /^(-?\d+)%$/;

/** @public */
class QualityQuery {
  constructor(queryStr) {
    if (!QUALITY_QUERY_PARSER_REGEX.test(queryStr)) {
      throw new Error(`品質「${queryStr}」語法有誤。`);
    }

    this.query = queryStr;

    if (RegExp.$2.length) {
      this.min = RegExp.$1.length ? parseInt(RegExp.$1, 10) : -Infinity;
      this.max = RegExp.$3.length ? parseInt(RegExp.$3, 10) : Infinity;
    } else {
      this.min = this.max = parseInt(RegExp.$1, 10);
    }

    if (this.max < this.min) {
      [this.min, this.max] = [this.max, this.min];
    }
  }

  /** @public */
  match(text) {
    if (QUALITY_QUERY_MATCHER_REGEX.test(text)) {
      const value = parseInt(RegExp.$1);
      return this.min <= value && value <= this.max;
    }
    return false;
  }
}

/** @public */
class SnippetsGenerator {
  constructor(text, keywords, {
    contextLength = 50,
    maxLength = 200,
    detailedMap = false,
  } = {}) {
    this.text = text;
    this.keywords = keywords;
    this.contextLength = contextLength;
    this.maxLength = maxLength;
    this.detailedMap = detailedMap;
    this.hitsMap = this.getHitsMap();
  }

  /** @public */
  run() {
    if (!this.hitsMap.size) {
      return this.text.substring(0, this.maxLength);
    }

    let snippet = this.getBestSnippet();
    snippet = this.adjustSnippet(snippet);

    return this.text.substring(snippet.start, snippet.end);
  }

  /** @public */
  markHits(callback) {
    const hits = [...this.hitsMap.values()]
      .reduce((rv, hits) => rv.concat(hits))
      .sort((a, b) => {
        if (a.start > b.start) { return 1; }
        if (a.start < b.start) { return -1; }
        if (a.keywordIndex > b.keywordIndex) { return 1; }
        if (a.keywordIndex < b.keywordIndex) { return 1; }
        return 0;
      });

    const rv = [];
    let lastIndex = 0;
    for (const hit of hits) {
      if (hit.start < lastIndex) { continue; }
      let delta = this.text.substring(lastIndex, hit.start);
      delta = callback(delta);
      rv.push(delta);
      let match = this.text.substring(hit.start, hit.end);
      match = callback(match, hit.keyword, hit.keywordIndex);
      rv.push(match);
      lastIndex = hit.end;
    }
    let delta = this.text.substring(lastIndex);
    delta = callback(delta);
    rv.push(delta);
    return rv.join('');
  }

  /** @private */
  getHitsMap() {
    const map = new Map();
    let keywordIndex = 0;
    for (const keyword of this.keywords) {
      const keywordMap = [];
      let lastIndex = keyword.lastIndex = 0;
      let m = keyword.exec(this.text);
      while (m) {
        const hit = {start: m.index, end: keyword.lastIndex};
        if (this.detailedMap) {
          Object.assign(hit, {
            keyword,
            keywordIndex,
          });
        }
        keywordMap.push(hit);

        // Proceed 1 char for a 0-length hit to prevent an infinite loop.
        // Note that lastIndex of /(?:)/gu could become smaller when it's
        // within a unicode surrogate pair.
        if (keyword.lastIndex <= lastIndex) {
          keyword.lastIndex = lastIndex + 1;
        }

        lastIndex = keyword.lastIndex;

        m = keyword.exec(this.text);
      }
      if (keywordMap.length) {
        map.set(keyword, keywordMap);
      }
      keywordIndex++;
    }
    return map;
  }

  /** @private */
  getBestSnippet() {
    const textLen = this.text.length;
    const snippet = {start: 0, end: 0};

    let bestSnippet = Object.assign({}, snippet);
    let bestKeywords = new Map();
    const cache = new Map();

    while (snippet.end <= textLen) {
      const keywords = this.getSnippetKeywords(snippet, {cache});

      // quickly break for a feasible snippet
      if (keywords.size === this.hitsMap.size) {
        Object.assign(bestSnippet, snippet);
        bestKeywords = keywords;
        break;
      }

      // compare and update the best snippet
      if (keywords.size > bestKeywords.size) {
        Object.assign(bestSnippet, snippet);
        bestKeywords = keywords;
      }

      snippet.end++;
      if (snippet.end - snippet.start > this.maxLength) {
        snippet.start++;
      }
    }

    // shrink the range to first start and last end of the first occurrence of all keywords
    if (bestKeywords.size) {
      let minStart = Infinity;
      let maxEnd = -Infinity;
      for (const [keyword, hit] of bestKeywords.entries()) {
        if (hit.start < minStart) { minStart = hit.start; }
        if (hit.end > maxEnd) { maxEnd = hit.end; }
      }

      return {start: minStart, end: maxEnd};
    }

    return bestSnippet;
  }

  /** @private */
  getSnippetKeywords(snippet, {cache} = {}) {
    let containedKeywords = new Map();
    for (const [keyword, hits] of this.hitsMap.entries()) {
      let foundFirstHit = false;
      const start = cache && cache.get(keyword) || 0;
      for (let i = start, I = hits.length; i < I; i++) {
        const hit = hits[i];
        if (hit.start < snippet.start) {
          continue;
        }

        // cache the first valid hit index to start faster for future runs
        if (!foundFirstHit) {
          if (i > start) {
            cache && cache.set(keyword, i);
          }
          foundFirstHit = true;
        }

        if (hit.start > snippet.end) {
          break;
        }
        if (snippet.start <= hit.start && hit.end <= snippet.end) {
          containedKeywords.set(keyword, hit);
          break;
        }
      }
    }
    return containedKeywords;
  }

  /** @private */
  adjustSnippet(snippet) {
    const textLength = this.text.length;
    const contextLength = Math.min(this.contextLength, Math.ceil((this.maxLength - (snippet.end - snippet.start)) / 2));

    const startAvail = snippet.start - 0;
    const endAvail = textLength - snippet.end;
    const startContextLength = Math.min(contextLength + Math.max(contextLength - endAvail, 0), startAvail);
    const endContextLength = Math.min(contextLength + Math.max(contextLength - startAvail, 0), endAvail);

    const newStart = Math.max(snippet.start - startContextLength, snippet.end - this.maxLength, 0);
    const newEnd = Math.min(snippet.end + endContextLength, newStart + this.maxLength, textLength);
    return {start: newStart, end: newEnd};
  }
}

return Object.assign(utils, {
  SynonymHandler,
  NoPuncHandler,
  ComplexQuery,
  KeywordQuery,
  DateQuery,
  QualityQuery,
  SnippetsGenerator,
});

}));
